package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/remove-nodes-from-linked-list">从链表中移除节点(Remove Nodes From Linked List)</a>
 * <p>给你一个链表的头节点 head 。</p>
 * <p>对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。</p>
 * <p>返回修改后链表的头节点 head 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [5,2,13,3,8]
 *      输出：[13,8]
 *      解释：需要移除的节点是 5 ，2 和 3 。
 *          - 节点 13 在节点 5 右侧。
 *          - 节点 13 在节点 2 右侧。
 *          - 节点 8 在节点 3 右侧。
 *
 * 示例 2：
 *      输入：head = [1,1,1,1]
 *      输出：[1,1,1,1]
 *      解释：每个节点的值都是 1 ，所以没有需要移除的节点。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>给定列表中的节点数目在范围 [1, 10^5] 内</li>
 * <li>1 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/5 11:24
 */
public class LC2487RemoveNodes_M {
    static class Solution {
        public ListNode removeNodes(ListNode head) {
            // 先反转
            head = reserve(head);
            // 移除元素
            ListNode currNode = head;
            while (currNode.next != null) {
                if (currNode.val > currNode.next.val) {
                    currNode.next = currNode.next.next;
                } else {
                    currNode = currNode.next;
                }
            }
            // 再反转
            return reserve(head);
        }

        private ListNode reserve(ListNode head) {
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }
}